#include <cstdio>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <queue>
#include <iostream>
using namespace std;
typedef struct BinaryTree{
    char data;
    BinaryTree *lson,*rson;
    BinaryTree(char d='#'):data(d),lson(nullptr),rson(nullptr){};
}BNode;
//按先序次序构造一颗二叉树
BNode* CreateBinaryTree(string &preStr,int& idx){
    if(preStr.size()==0 || idx==preStr.size() || preStr[idx]=='#'){
        return nullptr;
    }
    BNode *root=new BNode(preStr[idx++]);
    root->lson=CreateBinaryTree(preStr,idx);
    root->rson=CreateBinaryTree(preStr,++idx);
    return root;
}
//层次遍历
void bfs(BNode *root){
    if(root==NULL){
        return;
    }
    queue<BNode*> q;
    q.push(root);
    while(!q.empty()){
        int cnt=q.size();
        while(cnt--){
            BNode *tmp=q.front();
            q.pop();
            printf("当前节点为 %c ",tmp->data);
            if(tmp->lson){
                printf("左: %c ",tmp->lson->data);
                q.push(tmp->lson);
            }
            else{
                printf("左为空 ");
            }
            if(tmp->rson){
                printf("右： %c",tmp->rson->data);
                q.push(tmp->rson);
            }
            else{
                printf("右为空");
            }
            printf("\n");
        }
        printf("\n");
    }
}
void Exchange(BNode* &T){
    BNode *tmp;
    if(T){
        tmp=T->lson;
        T->lson=T->rson;
        T->rson=tmp;
        Exchange(T->lson);
        Exchange(T->rson);
    }
    return;
}
int main(void){
    printf("输入先序遍历序列\n");
    //string s="abc##d##e#f##";
    string s;
    cin >> s;
    int idx=0;
    BNode *root=CreateBinaryTree(s,idx);
    printf("原始的树:\n");
    bfs(root);
    Exchange(root);
    printf("左右子树互换:\n");
    bfs(root);
    return 0;
}